/*************************************************************************
	> File Name: heap_sort.cpp
	> Author: zhangxu
	> Mail: 
	> Created Time: 二  8/20 18:38:50 2024
 ************************************************************************/

// #include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstdlib>
#include "1.sort_test.h"
#define ROOT 1
#define CMP >
#define FATHER(i) ((i) / 2)
#define LEFT(i)   ((i) * 2)
#define RIGHT(i)  ((i) * 2 + 1)

inline void upMaintain(int *data, int i) {
	while(i > ROOT && data[i] CMP data[FATHER(i)]) {
		swap(data[i], data[FATHER(i)]);
		i = FATHER(i);
	}
	return ;
}

inline void downMaintain(int *data, int i, int n) {
	while(LEFT(i) <= n) {
		int ind = i, l = LEFT(i), r = RIGHT(i);
		if(data[l] CMP data[ind]) ind = l;
		if(r <= n && data[r] CMP data[ind]) ind = r;
		if(ind == i) break;
		swap(data[ind], data[i]);
		i = ind;
	}
	return ;
}

inline void normalHeapBuild(int *data, int n) {
	for(int i = 2; i <= n; i++) {
		upMaintain(data, i);
	}
	return ;
}

inline void linearHeapBuild(int *data, int n) {
	for(int i = n / 2; i >= ROOT; i--) {
		downMaintain(data, i, n);
	}
	return ;
}

void heapSortFinal(int *data, int n) {
	for(int i = n; i >= 2; i--) {
		swap(data[ROOT], data[i]);
		downMaintain(data, ROOT, i - 1);
	}
	return ;
}

void normalHeap(int *arr, int n) {
	int *data = arr - 1;
	normalHeapBuild(data, n);
	heapSortFinal(data , n);
	return ;
}

void linearHeap(int *arr, int n) {
	int *data = arr - 1;
	linearHeapBuild(data, n);
	heapSortFinal(data, n);
	return ;
}

int main() {
	int *arr = getRandData(BIG_DATA);
	TEST(normalHeap, arr, BIG_DATA);
	TEST(linearHeap, arr, BIG_DATA);
	return 0;
}